package Leetcode;

import base.ListNode;

/**
 * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 */
public class 力扣21_合并两个有序链表 {

    public static void main(String[] args) {
        ListNode a = new ListNode(3);
        ListNode b = new ListNode(6);
        ListNode c = new ListNode(11);
        ListNode d = new ListNode(23);
        ListNode e = new ListNode(30);
        a.next = b;
        b.next = c;
        c.next = d;
        d.next = e;

        ListNode a2 = new ListNode(1);
        ListNode b2 = new ListNode(5);
        ListNode c2 = new ListNode(18);
        ListNode d2 = new ListNode(20);
        ListNode e2 = new ListNode(28);
        a2.next = b2;
        b2.next = c2;
        c2.next = d2;
        d2.next = e2;

        ListNode listNode = mergeTwoLists(a, a2);
        System.out.println(listNode);
    }

    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }

        // 定义一个头部 用来标记链表头节点
        ListNode head = new ListNode(0);
        // 用来标记链表尾节点
        ListNode tail = head;

        // 比较两个数值是否相同
        while (list1 != null && list2 != null) {
            int val1 = list1.val;
            int val2 = list2.val;
            if (val2 <= val1) {
                tail.next = list2;
                tail = list2;
                list2 = list2.next;
            } else {
                tail.next = list1;
                tail = list1;
                list1 = list1.next;
            }
        }

        // 最后肯定有一个链表不为空 可直接拼接最后
        if (list1 != null) {
            tail.next = list1;
        }
        if (list2 != null) {
            tail.next = list2;
        }

        // 返回自定义链表头结点的下一个节点
        return head.next;
    }

    // 双重for循环暴力解决
    public static ListNode mergeTwoLists2(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        ListNode head = new ListNode(0);
        ListNode tail = head;
        while (list1 != null) {
            while (list2 != null) {
                int val1 = list1.val;
                int val2 = list2.val;
                if (val2 <= val1) {
                    tail.next = list2;
                    tail = list2;
                    list2 = list2.next;
                } else {
                    break;
                }
            }
            tail.next = list1;
            tail = list1;
            list1 = list1.next;
        }
        return head.next;
    }

}
